#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

ll read(){ll x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int N = 510,M = 1e5 + 10,S = 15;
const int mod = 999911659;

int f[N][S][N],b[M],gap,stp,len,P,vis[N],C[N][S],fac[S],ifac[S];
ll n,cnt[N];

ll qp(ll x,int t){ll res = 1;for(;t;t >>= 1,x = x * x % mod) if(t & 1) res = res * x % mod;return res;}

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,P = in;
	for(int i = 1;i < M * 100;i++){b[i] = (b[i-1] * 10 + 1) % P; if(vis[b[i]]){len = i; stp = vis[b[i]];break;} vis[b[i]] = i;}
	for(int i = 1;i <= min(stp - 1ll,n);i++) cnt[b[i]]++; gap = len - stp; int tot = 0;
	for(int i = stp;i < len;i++){
		cnt[b[i]] += (n / gap + (i % gap <= n % gap) - ((stp - 1) / gap + ((stp - 1) % gap >= i % gap)));
		cnt[b[i]] %= mod; if(i % gap == n % gap) tot = b[i];
	}
	for(int i = (fac[0] = 1);i < S;i++) fac[i] = (ll) fac[i-1] * i % mod; ifac[S - 1] = qp(fac[S - 1],mod-2);
	for(int i = S - 2;~i;i--) ifac[i] = (ll) ifac[i + 1] * (i + 1) % mod;
	for(int i = 0;i < P;i++){
		if(!cnt[i]) {C[i][0] = 1; continue;}
		C[i][0] = 1; for(int j = 1;j < S;j++) C[i][j] = (ll) C[i][j-1] * ((cnt[i] + j - 1) % mod) % mod * fac[j - 1] % mod * ifac[j] % mod;
	}
	for(int i = 0;i < 9;i++) f[0][i][0] = C[0][i];
	for(int i = 1;i < P;i++)
		for(int j = 0;j < 9;j++)
			for(int s = 0;s < P;s++)
				for(int k = 0;k <= j;k++)
					f[i][j][s] = (f[i][j][s] + (ll) f[i-1][j - k][((s - k * i) % P + P) % P] * C[i][k] % mod) % mod;
	int ans = 0; for(int i = 0;i < 9;i++) ans = (ans + f[P - 1][i][(P - tot) % P]) % mod; printf("%d\n",ans);
	return 0;
}
